/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-01-27
 * Time: 10:12
 */
public class Test {

    public static void createRing(ListNode headA, ListNode headB){
        headA.next.next = headB.next.next;
    }

    // 输入两个链表，找出它们的第一个公共结点
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null){
            return null;
        }
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while(pl!=null){
            lenA++;
            pl = pl.next;
        }
        pl = headA;
        while(ps!=null){
            lenB++;
            ps = ps.next;
        }
        ps = headB;
        //求差值
        int len = lenA - lenB;
        if(len<0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //pl指向了最长的链表，ps指向了最短的链表，len为差值步
        //让pl先走len步
        while(len>0){
            pl = pl.next;
            len--;
        }
        //pl 与 ps 同时走，当pl与pl相遇就结束
        while(pl!=ps){
            pl = pl.next;
            ps = ps.next;
            if(pl==null || ps==null){
                return null;
            }
        }
        return pl;
    }

    public static void main(String[] args) {
        MyList myList = new MyList();
        myList.addFirst(10);
        myList.addFirst(20);
        myList.addFirst(30);
        myList.addFirst(40);
        myList.addFirst(50);
        //myList.createPoot();
        boolean ret = myList.hasCycle();
        System.out.println(ret);
    }
    public static void main1(String[] args) {
        MyList myList1 = new MyList();
        myList1.addFirst(10);
        myList1.addFirst(20);
        myList1.addFirst(30);
        myList1.addFirst(40);
        myList1.addFirst(50);

        MyList myList2 = new MyList();
        myList2.addFirst(11);
        myList2.addFirst(21);
        myList2.addFirst(31);
        myList2.addFirst(41);
        createRing(myList1.head, myList2.head);
        ListNode ret = getIntersectionNode(myList1.head, myList2.head);
        System.out.println(ret.value);

        MyList myList =new MyList();
       for (int i = 5; i <11 ; i++) {
           myList.addLast(i);
       }
        myList.display();
        System.out.println("============");

        //查找链表中是否包含数据6
        System.out.println(myList.contains(6));
        System.out.println("============");

        //返回链表的长度
        System.out.println(myList.size());
        System.out.println("============");

        //头插法
        myList.addFirst(2);
        myList.display();
        System.out.println("============");

        //尾插法
        myList.addLast(15);
        myList.display();
        System.out.println("============");

        //任意位置插入,第一个数据节点为0号下标
        myList.addIndex(2,20);
        myList.display();
        System.out.println("============");

        //删除第一次出现关键字为key的节点
        myList.remove(3);
        System.out.println("============");

        myList.clear();
    }
}
